Вычислимая функция - définition. Qu'est-ce que Вычислимая функция
Diclib.com
Dictionnaire ChatGPT
Entrez un mot ou une phrase dans n'importe quelle langue 👆
Langue:

Traduction et analyse de mots par intelligence artificielle ChatGPT

Sur cette page, vous pouvez obtenir une analyse détaillée d'un mot ou d'une phrase, réalisée à l'aide de la meilleure technologie d'intelligence artificielle à ce jour:

  • comment le mot est utilisé
  • fréquence d'utilisation
  • il est utilisé plus souvent dans le discours oral ou écrit
  • options de traduction de mots
  • exemples d'utilisation (plusieurs phrases avec traduction)
  • étymologie

Qu'est-ce (qui) est Вычислимая функция - définition

Вычислимые функции

Вычислимая функция         

одно из основных понятий теории алгоритмов. Функция f называется вычислимой, если существует Алгоритм, перерабатывающий всякий объект х, для которого определена функция f, в объект f (x) и не применимый ни к какому x, для которого f не определена. Примеры: х - натуральное число, f (x) = х2; x - пара рациональных чисел x1 и x2, f (x) = x1: x2 (эта функция определена лишь для тех x, у которых x2 ≠0); X - пара матриц (См. Матрица) X1 и X2 с целочисленными элементами, f (X) = X1X2 (эта функция определена лишь для тех X, у которых число стоблцов в X1 совпадает с числом строк в X2). Аргументами и значениями В. ф. могут быть лишь так называемые конструктивные объекты (см. Конструктивное направление в математике) (ибо лишь с такими объектами могут оперировать алгоритмы); таким образом, функция f такая, что f (x) ≡ х не является вычислимой, если её рассматривать на всей действительной прямой, но является вычислимой, если её рассматривать как функцию натурального или рационального аргумента. В. ф., областью определения которой служит натуральный ряд, называется вычислимой последовательностью.

В. А. Успенский.

Вычислимая функция         
Вычислимые функции — это множество функций вида, f\colon N \to N, которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции f называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию.
Односторонняя функция         
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений.

Wikipédia

Вычислимая функция

Вычислимые функции — это множество функций вида, f : N N , {\displaystyle f\colon N\to N,} которые могут быть реализованы на машине Тьюринга. Задачу вычисления функции f {\displaystyle f} называют алгоритмически разрешимой или алгоритмически неразрешимой, в зависимости от того, возможен ли алгоритм, вычисляющий эту функцию.

В качестве множества N {\displaystyle N} обычно рассматривается множество B {\displaystyle B^{*}}  — множество слов в двоичном алфавите B = { 0 , 1 } {\displaystyle B=\{0,1\}} , с оговоркой, что результатом вычисления может быть не только слово, но и специальное значение «неопределённость», соответствующее случаю, когда алгоритм «зависает». Таким образом, можно дать следующее определение N {\displaystyle N} :

N = B { undef } , {\displaystyle N=B^{*}\cup \{\operatorname {undef} \},}

где B = { 0 , 1 } {\displaystyle B=\{0,1\}} , а undef {\displaystyle \operatorname {undef} }  — специальный элемент, означающий неопределённость.

Роль множества N {\displaystyle N} может играть множество натуральных чисел, к которому добавлен элемент undef {\displaystyle \operatorname {undef} } , и тогда вычислимые функции — это некоторое подмножество натуральнозначных функций натурального аргумента. Удобно считать, что в качестве N {\displaystyle N} могут выступать различные счётные множества — множество натуральных чисел, множество рациональных чисел, множество слов в каком-либо конечном алфавите и др. Важно, чтобы существовал некоторый формальный язык в конечном алфавите описания элементов множества N {\displaystyle N} и чтобы задача распознавания корректных описаний была вычислима. Например, для описания натуральных чисел удобно использовать двоичную систему счисления — язык описания натуральных чисел в алфавите B {\displaystyle B} .

В данном определении вместо исполнителя машин Тьюринга можно взять один из Тьюринг-полных исполнителей. Грубо говоря, «эталонным исполнителем» может быть некоторый абстрактный компьютер, подобный используемым персональным компьютерам, но с потенциально бесконечной памятью и особенностями архитектуры, позволяющими использовать эту бесконечную память.

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому множество вычислимых функций не более чем счётно, в то время как множество функций вида f : N N , {\displaystyle f\colon N\to N,} несчётно, если N {\displaystyle N} счётно. Значит, есть невычислимые функции, причём мощность их множества больше, чем мощность множества вычислимых функций. Примером невычислимой функции (алгоритмически неразрешимой проблемы) может быть функция определения остановки — функция, которая получает на вход описание некоторой машины Тьюринга и вход для неё, а возвращает 0 или 1 в зависимости от того, остановится данная машина на данном входе или нет. Ещё одним примером невычислимой функции является колмогоровская сложность.

Qu'est-ce que Вычисл<font color="red">и</font>мая ф<font color="red">у</font>нкция - définition